package com.yx.study.leet.questionList.questions;

import org.junit.Test;

/**
 * 28. 找出字符串中第一个匹配项的下标
 * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
 */
public class Solution28 {
    public int strStr(String haystack, String needle) {
        int index = 0;
        int child = 0;
        boolean flag = false;
        char[] haystackChar = haystack.toCharArray();
        char[] needleChar = needle.toCharArray();
        for (int i = 0; i < haystack.length(); i++) {
            if (haystackChar[i] == needleChar[child]) {
                if (child == 0) {
                    if (haystack.length() - i < needle.length()) {
                        break;
                    }
                    index = i; // 保存比对的初始下标
                    flag = true;
                }
                if (child == needle.length() - 1) {
                    break;
                }
                child++;
            } else {
                if (flag) {
                    i = index;
                    flag = false;
                }
                child = 0;
                index = 0;
            }
        }
        if (child != needle.length() - 1 || needleChar[0] != haystackChar[index]) { // 只匹配了一部分子串,父串就匹配结束了
            index = -1;
        }
        return index;
    }

    @Test
    public void test() {
        //"aabaaabaaac"
        //"aabaaac"
        System.out.println(strStr("aabaaabaaac", "aabaaac"));
        System.out.println(strStrGlobal("aabaaabaaac", "aabaaac"));
    }

    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStrGlobal(String ss, String pp) {
        if (pp.isEmpty()) return 0;

        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }
}
